Peripheral storage hierarchies have been used for years for providing an apparent store as suggested by Eden, et al in U.S. Pat. No. 3,569,938. Eden, et al teach that in a demand paging or request system, caching data in a cachetype, high-speed front store (buffer) can make a peripheral storage system appear to have a large capacity, yet provide rapid access to data; rapid access being faster than that provided by the normal backing store. Eden, et al also teach that the backing store can be a retentive store, such as magnetic tape recorders and magnetic disk recorders while the front store can be a volatile store, such as a magnetic core store. With the advances in data-storage technology, the front store typically includes semiconductive type data-storage elements. U.S. Pat. No. 3,839,704 shows another form of such a storage hierarchy. An important aspect of storage hierarchies is good performance at low cost.
Storage hierarchies have taken diverse forms. For example, in accordance with the Eden, et al U.S. Pat. No. 3,569,938 a single high-speed store serviced several users. U.S. Pat. No. 3,735,360 shows that each processor can have its own high-speed store or cache. Performance of storage hierarchies also is affected by the algorithms and other controls used to place predetermined data into the cache or high-speed storage portion. Along this line, U.S. Pat. No. 3,898,624 shows that varying the time of fetching data from a backing store to a front or caching store can be selected by computer operator in accordance with the programs being executed in a using CPU. In this manner, it is hoped that the data resident in the cache or upper level of the hierarchy will be that data needed by the CPU while other excess data is not resident in the cache. This arrangement allows more useful data to be stored in the higher level storage portion. All of these operations become quite intricate. Accordingly, evaluation programs for storage hierarchies have been used to evaluate how best to manage a storage hierarchy. U.S. Pat. Nos. 3,964,028 and 4,068,304 show performance monitoring of storage hierarchies for achieving these goals. Even at that, much remains to be done in various types of storage hierarchies for enhancing optimum performance while ensuring data integrity. Much of the work with respect to storage hierarchies has occurred in the cache and main memory combinations connected to a using CPU. The principles and teachings from a cached main memory relate directly to caching and buffering peripheral systems, as originally suggested by Eden et al, supra. Of course, main memory has been used prior to Eden, et al for buffering or caching data from a magnetic tape and disk unit for a CPU, i.e. a main memory was not only used as a CPU working store but also as a buffer for peripheral devices.
The performance monitoring referred to above has indicated that it is not always in the best interests of total data-processing performance and integrity to always use a caching buffer interposed between a using unit and a backing store. For example, U.S. Pat. No. 4,075,686 teaches that a cache can be turned on and off by special instructions for selectively bypassing the cache. Further, the backing store or memory was segmented into various devices with some of the devices or segments being bypassed, such as for serial or sequential input/output operations. U.S. Pat. No. 4,268,907 teaches that for a command specifying the fetching of data words, an indicator flag is set to a predetermined state. Such flag conditions replacement circuits to respond to subsequent predetermined commands to bypass cache storage for subsequently fetched data words when the indicator flag is in the predetermined state to prevent replacement of extensive numbers of data instructions already stored in cache during the execution of such instructions. Interestingly, U.S. Pat. No. 4,189,770 shows bypassing cache for operands, but using cache for storing instructions.
Disk storage apparatus, also referred to as direct access storage devices (DASD), provide large quantities of random-access nonvolatile data-storage for data processing. Caching the DASD, as suggested above, provides a storage hierarchy with the performance and throughput capability better than that of DASD. Such performance improvement is obtained principally by maximizing the number of data-storage accesses which can be satisfied by accessing a copy of the data in the cache rather than by directly accessing the DASD. Management of the data-storage hierarchy includes dynamically entering data into and deleting data from the cache with the intent of increasing the proportion of the number of accesses that can be satisfied through the cache. While such management tends to reduce the size of a front store for controlling its costs, it has been observed that data does not always fill the record tracks of DASD, hence further savings may be available. All of the above shows a need for carefully managing utilization of data-storage space in a front store for controlling its costs. Such cost control is important where large blocks of data, such as 30 kilobytes or more are cached in a front store and such blocks are not always filled with data signals.
The management of data-storage apparatus for ensuring full utilization of such space available in any data storage unit includes storing variable-length data. For example, U.S. Pat. No. 3,739,352, shows a microprogrammed processor associated with a so-called "free-field" memory in which operands of any length in terms of number of bits can be processed. The free-field memory is addressed by an address register that points to the boundary between any two bits stored in the memory as the start of a field and indicates the number of bits in the field up to a maximum bit capacity of the memory. While this technique certainly appears to provide for a maximal packing of a given memory (data-storage unit), when such data is replaced by other data the probability of the replacing data having an extent (number of bits) equal to the data being replaced is relatively small. This means that each time data is replaced that the memory must be reformatted if the storage efficiency is to be maintained. Accordingly, this technique, while probably valuable for many applications, is not applicable to a front-store/back-store data-storage hierarchy because of the data replacement operations. As a result of such a scheme, it can be easily envisioned that fragmentation of data would occur which requires extensive and time-consuming management techniques not desired in a peripheral data-storage hierarchy.
A second U.S. Pat. No. 3,824,561 relates to storing groups of variable-length data elements which are allocated to storage addresses by means of apparatus and methods using characteristic data sets which define the characteristics of each data element in the group to be stored. This technique requires that the data sets be scanned in two directions. On a first pass, information as to the length and boundary requirements of each element are accumulated, then on a second pass addresses are allocated to each element to eliminate gaps in the group while maintaining proper boundary alignment. Again, this technique has value in certain applications but in the data-storage hierarchy, the replacment requirements plus the requirement of relatively low cost prohibit the complicated control. Performance requirements of a peripheral data-storage hierarchy are at odds with the first and second time-consuming pass requirements for doing an allocation. Accordingly, while this technique can provide efficient utilization of a data-storage unit, the techniques are not applicable to a data-storage hierarchy front store management where replacement and performance are intermingled with allocations of data-storage space for variable length data.
U.S. Pat. No. 4,027,288 shows using a character set including a beginning delimiter character and an ending delimiter character such that information segments may be of any length up to the capacity of the storage mechanism. Automatic data-storage allocation and reclamation of unused storage space as strings of data increase or decrease in size is provided for. This system employs symbolic addressing data on a magnetic tape wherein delimiter signals and sequential operations can take advantage of the described data-packing technique. For a random-access memory which is found in most front stores of a data-storage hierarchy, this technique is not applicable for achieving data packing while maintaining low cost and good performance.
U.S. Pat. No. 4,035,778 shows allocation of working space in a main memory of a host processor which optimizes the allocation by adjusting the size of the working set for each competing program. In a sense, the working memory can be considered as a buffer in the data-storage hierarchy wherein the host processor has a close-working association with the front store, i.e. the working memory. The techniques of this patent also relate to replacement controls such that the allocations of the working space is adjusted through replacement techniques. Peripheral data-storage hierarchies, because of the loose-coupling to the host processor, cannot take advantage of the described technique.
In a peripheral data-storage unit, U.S. Pat. No. 4,103,329 shows handling data represented by variable field length for using less data-storage. The bit fields are handled independently in the natural storage addressing elements and boundaries. This patent shows initializing a displacement register to contain an element displacement from a base address which contains the first bit of a desired bit field. While such a technique is certainly appropriate for packing data into a main memory for use by a host processor, the complexity and tracking of all of such data wherein the quantity of data is in the megabyte range becomes excessively expensive. Accordingly, these later-described techniques are also not fully satisfactory for managing a front store of a peripheral data-storage hierarchy.
Yet other techniques employed for improving utilization of data-storage apparatus include that described in the IBM TECHNICAL DISCLOSURE BULLETIN by Paddock, et al, Vol. 14, No. 7, December 1971, pages 1955 through 1957. This article shows an asymmetrical high-speed storage consisting of an 8 KB (kilobytes) area and two 4 KB areas, each area has a separate directory. Apparently smaller sets of data would be stored in the 4 KB areas while larger sets of data would be stored in the 8 KB area. Such a technique does not address the suitability of managing a front store where relatively large blocks of variable length data, i.e. 30 KB or greater are to be transferred as units. In another IBM TECHNICAL DISCLOSURE BULLETIN article by Gates, et al, "Multiword Size Storage" in Vol. 14, No. 8, January, 1969, pages 1019-1020 shows managing a data-storage apparatus for avoiding wasting or nonuse of storage bits due to difference in word sizes of data. The techniques of this article relate to storing words having two different sizes and alternating the storage such that no unused disks are employed. This article approaches the management of a data-storage apparatus only for an extremely limited set of data formats and hence is not applicable to a general storage apparatus.
Even with all of the above-described apparatus and techniques for managing a data-storage apparatus for maximizing utilization. There still is needed a relatively simple but effective management apparatus and method which can handle large units of data at relatively low cost while maximizing data-storage utilization and preserving high performance.